package com.jc.projecteuler.january;

/**
 * 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
 * <p>
 * What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
 * <p>
 * 其实这道题，笔算也可以算，就是求最大公因数 第一步。将1~20进行因数分解，才把各个因数相乘起来，这里的相乘是因数相同的，最大有多少个，则多少次方，
 * 则公式= 2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19 = 232792560
 * <p>
 * 编程算则有
 * 1. 穷举法 性能比较差
 * 2. 根据上面的笔算得出来的公式，其实就是，质因数的N次方累乘，其中N的公式等于 exponentiation = Math.floor(Math.log(k)/Math.log(p[pi]))
 */
public class Problem5 {

    public static void main(String[] args) {
//        System.out.println(2^4);  - -注，Java没有这样的幂运算，这个^是位异或, 2^4=6
        int leastCommonMultiple = 1;
        long begin = System.currentTimeMillis();
        while (!isEvenlyDivisible(leastCommonMultiple)) {
            leastCommonMultiple++;
        }

        System.out.println("METHOD1. evenly divisible by all of the numbers from 1 to 20 is " + leastCommonMultiple + " cost " + (System.currentTimeMillis() - begin) + "ms");


        leastCommonMultiple = 1;
        int[] p = {2, 3, 5, 7, 11, 13, 17, 19};
        long begin2 = System.currentTimeMillis();
        int k = 20;
        for (int pi = 0; pi < p.length; pi++) {
            double exponentiation = Math.floor(Math.log(k) / Math.log(p[pi]));
            leastCommonMultiple *= Math.pow(p[pi], exponentiation);
        }

        System.out.println("METHOD2. evenly divisible by all of the numbers from 1 to 20 is " + leastCommonMultiple + " cost " + (System.currentTimeMillis() - begin2) + "ms");

    }

    /**
     * output:
     * METHOD1. evenly divisible by all of the numbers from 1 to 20 is 232792560 cost 379ms
     * METHOD2. evenly divisible by all of the numbers from 1 to 20 is 232792560 cost 0ms
     */

    private static boolean isEvenlyDivisible(int leastCommonMultiple) {
        for (int i = 1; i <= 20; i++) {
            if (leastCommonMultiple % i != 0) {
                return false;
            }
        }
        return true;
    }
}
